import java.util.ArrayDeque;
import java.util.Deque;

public class Leetcode {
}

//leetcode:227：基本计算器II
class Solution {
    public int calculate(String s) {
       Deque<Integer> q = new ArrayDeque<Integer>();
       //将符号设为'+',是为了保证第一个数不变的情况下将第一个数放入栈中
       char pre = '+';
       int n = s.length();
       char[] ch = s.toCharArray();
       int i = 0;
       while (i < n) {
        int tmp = 0;
        //如果为空继续往下走
        if(ch[i] == ' ') i++;
        //如果为数字
        else if (ch[i] >= '0' && ch[i] <='9') {
            //将连在一起的数字形成整体
            while(i < n && ch[i] >= '0' && ch[i] <='9') {
                tmp = tmp * 10 + (ch[i] - '0');
                i++;
            }
            //如果符号为+或-,直接放入栈中
            if(pre == '+') q.push(tmp);
            else if(pre == '-') q.push(-tmp);
            //如果符号位*或/，将栈顶元素与此时的数进行运算
            else if(pre == '*') q.push(q.pop() * tmp);
            else if(pre == '/') q.push(q.pop() / tmp);
        }
        //如果此时的字符位，符号就更新pre的符号，并继续走
        else {
           pre = ch[i];
           i++;
        }
       }
    //最后，将栈中的所有元素进行相加
    int ret = 0;
    while(!q.isEmpty()) {
        ret += q.pop();
    }
    return ret;
    }
}

